Motor Sport 12 1959 UK

arXiv:1111.1567v2 [nlin.CG] 7 Dec 2011

Generalization of Conway’s ” Game of Life" to a
continuous domain - SmoothLife

Stephan Rafler
Niirnberg, Germany
fr Indmr @ web. de

December 8, 2011

Abstract

We present what we argue is the generic generalization of Conway’s
” Game of Life” to a continuous domain. We describe the theoretical model
and the explicit implementation on a computer.

1 Introduction

There have been many generalizations of Conway’s ’’Game of Life” (GoL) since
its invention in 1970 pQ. Almost all attributes of the GoL can be altered: the
number of states, the grid, the number of neighbors, the rules. One feature
of the original GoL is the glider, a stable structure that moves diagonally on
the underlying square grid. There are also ’’spaceships”, similar structures that
move horizontally or vertically.

Attempts to construct gliders (as we will call all such structures in the fol¬
lowing), that move neither diagonally nor straight, have led to huge man-made
constructions in the original GoL. An other possibility to achieve this has been
investigated by Evans [2], namely the enlargement of the neighborhood. It has
been called ’’Larger than Life” (LtL). Instead of 8 neighbors the neighborhood
is now best described by a radius r, and a cell having (2r + l) 2 — 1 neighbors.
The rules can be arbitrarily complex, but for the start it is sensible to consider
only such rules that can be described by two intervals. They are called ’’birth”
and ’’death” intervals and are determined by two values each. These values can
be given explicitly as the number of neighbors or by a filling, a real number
between 0 and 1. In the first case, the radius has to be given, too, in the last
case, this can be omitted.

The natural extension of Evans’ model is to let the radius of the neighbor¬
hood tend to infinity and call this the continuum limit. The cell itself becomes
an infinitesimal point in this case. This has been done by Pivato 0] and inves¬
tigated mathematically. He has called this model ’’RealLife” and has given a
set of ’’still lives”, structures that do not evolve with time.

1

2 SmoothLife

We take a slightly different approach and let the cell not be infinitesimal but of
a finite size. Let the form of the cell be a circle (disk) in the following, although
it could be any other closed set. Then, the ’’dead or alive” state of the cell is
not determined by the function value at a point x. but by the filling of the circle
around that point. Similarly, the filling of the neighborhood is considered. Let
the neighborhood be ring shaped, then with f(x, t) our state function at time t
we can determine the filling of the cell or ’’inner filling” m by the integral

M

du f(x + u, t)

|«|<r

and the neighborhood or ’’outer filling” n by the integral

(1)

n =

1

N

du f(x + u,t )

ri<\u\<r a

( 2 )

where N and M are normalization factors such that the filling is between
0 and 1. Because the function values of f lie also between 0 and 1 the factors
simply consist of the respective areas of disk and ring. The radius of the disk
or ’’inner radius” is given by r,; which is also the inner radius of the ring. The
outer radius of the ring is given by r a .

In the original GoL the state of a cell for the next time-step is determined
by two numbers: the live-state of the cell itself, which is 0 or 1, and the number
of live neighbors, which can be between 0 and 8. One could model all general
rules possible by a 2 x 9 matrix containing the new states for the respective
combinations. It could be called the transition matrix.

Now in our case this translates to the new state of the point x being de¬
termined by the two numbers in and n. The new state is given by a function
s(n,m). Let us call it the transition function. It is defined on the interval
[0,1] x [0,1] and has values in the range [0,1], To resemble the corresponding
situation in GoL, typically r a = 3r* is chosen (the diameter of the neighborhood
is 3 cells wide).

3 Computer implementation

As simple as the theoretical model is, it is not immediately obvious, how to
implement it on a computer, as a computer cannot handle infinitesimal values,
continuous domains, etc. But it can handle real numbers in the form of floating
point math, and as it turns out, this is sufficient. We also can model the
continuous domain by a square grid, the ideal data structure for computation.
So we will be able to implement our function f(x,t) as a float array.

When implementing the circularly shaped integrals we run into a problem.
Pixelated circles typically have jagged rims. So either we let the radius of
the circle be so huge, that the pixelation due to our underlying square grid is
negligible. Then the computation time will be enormous. Or we use another
solution used in many similar situations: anti-aliasing. Consider for example
the integration of the inner region. For the cell x function values are taken at

2

locations x + u. Let us define l = |u|. With an anti-aliasing zone around the
rim of width b we take the function value as it is, when l < ry — b/2. In the
case when l > ry + b/2 we take 0. In between we multiply the function value
by (ry + b/2 — l)/b. Similarly for the inner rim of the ring and the outer rim.
In this way the information on how far the nearest grid point is away from the
true circle, is retained. Typically, b = 1 is chosen.

We also have to construct the transition function s(n, to) explicitly. Luckily
we can restrict ourselves like LtL, for the beginning, to four parameters: the
boundaries of the birth and death intervals. To make things smooth and to
stay in the spirit of the above described anti-aliasing we use smooth step func¬
tions instead of hard steps. We call them sigmoid functions to emphasize this
smoothness. For example we could define

crUx, a) = - - 7—7 - . , . - (3)

1 + exp(— (x — a)4/a)

cr 2 (x,a,b) = a x (x,a) (1 - a x (x,b)) (4)

a m (x,y,m) = x(l - oi(to, 0.5)) + yai(m, 0.5) (5)

then we can define the transition function as

s(n,m) = cr 2 (n,a m {b 1 ,d 1 ,m),a m (b 2 ,d 2 , to)) (6)

where birth and death intervals are given by [&i, b 2 ] and [d\,d 2 \ respectively.
The width of the step is given by a. As we have two different types of steps
we have an a n and an a m . Note that neither the anti-aliasing nor the smooth¬
ness of the transition function are necessary for the computer simulation to
work. They just make things smoother and allow one to choose smaller radii
for neighborhood and inner region and so achieve faster computation times for
the time-steps.

4 Smooth time-stepping

So far we have made everything smooth and continuous but one thing: the
time-steps are still discrete. At time t, the function s(n,m) is calculated for
every x and this gives the new value f(x,t + 1) at time t + 1. If we think of the
application of s(n, m) as a nonlinear operator S we can write

f(x,t + 1) = S[s(n,m)] f(x,t) (7)

To give us the ability to obtain arbitrarily small time steps, we introduce an
infinitesimal time dt and reinterpret the transition function as a rate of change
of the function f(x,t) instead of the new function value. Then we can write

f(x, t + dt) = f(x, t ) + dt S'[s(?r, to)] f(x, t) (8)

where we have defined a new s(n,m), that has values in the range [—1,1]
instead of [0,1]. If the transition function in the discrete time-stepping scheme
was Sd(n, to) then the smooth one is s(n, to) = 2 Sd(n, to) — 1. The formula above
is also the most trivial integration scheme for the integro-differential equation

3

dtf(x, t ) = S[s(n, m)\ f(x, t) (9)

This equation however leads to a different form of life. The same generic
gliders can not be found at the same birth/death values as in the version with
discrete time-stepping, but it also leads to gliders, oscillating and stable struc¬
tures.

5 Conclusions

We have described a model to generalize Conway’s ” Game of Life” to a contin¬
uous range of values and a continuous domain. The 2x9 transition matrix of
the GoL has been generalized to the s(n,m) transition function. The 8 pixel
neighborhood and 1 pixel cell of GoL have been generalized to a ring shaped
neighborhood and a disk shaped cell. The rule set has been generalized to
four real numbers: the boundaries of the birth and death intervals. The last
remaining discrete attribute was the time-stepping. We proposed a method
for continuous time-stepping which reinterprets the transition function as the
velocity of change.

The technique with two radii has been used in other contexts [4j, but no
gliders were described. There has also been a computer implementation of
a continuous version of GoL, but without the inner radius technique, and no
gliders were found at that time [5].

The goal of finding a glider that can move in arbitrary directions has been
achieved. Of the original GoL it resembles both the glider and the spaceship at
the same time. It also resembles similar structures found in LtL. So we think
we have found the generic, generalized glider, and call it the ’’smooth glider”.

3

Figure 1: the smooth glider for r a = 21, b\ = 0.278, b 2 = 0.365, d\ =
0.267, d 2 = 0.445, a n = 0.028, a m = 0.147 as it moves to the upper right

References

[1] Conway’s’’Game of Life”, 1970

[2] ’’Larger than Life; it’s so nonlinear”, Kellie Michele Evans, PhD thesis, 1996

[3] ’’RealLife: the continuum limit of Larger Than Life cellular automata”,
Marcus Pivato, 2007

[4] ’’Dynamics of Complex Systems”, Yaneer Bar-Yam, 1997, (section 7.2: pat¬
tern formation)

[5] ’’Continuous Spatial Automata”, Bruce J. MacLennan, 1990

4